package com.monday.greedy.algorithm;

import lombok.Data;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 贪心算法--背包问题（可分割）
 *   假设我们有一个可以容纳 100kg 物品的背包，可以装各种物品。
 *   我们有以下 5 种豆子，每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大，
 *   我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？
 */
public class BackpackSeparable {

    // 物品重量
    private static Goods[] goodsList = new Goods[] {
              new Goods("黄豆",100, "100")
            , new Goods("绿豆",30, "90")
            , new Goods("红豆",60, "120")
            , new Goods("黑豆",20, "80")
            , new Goods("青豆",50, "75")

    };

    private static final int capacity = 10;

    public static void main(String[] args) {
        List<Goods> result = new BackpackSeparable().greedy();
        result.stream().forEach(System.out::println);
    }

    private List<Goods> greedy() {
        List<Goods> result = new ArrayList<>();

        // 按照单位价值排序
        Arrays.sort(goodsList, (o1, o2) -> o2.getUnitValue().compareTo(o1.getUnitValue()));


        // 从单位价值最高的物品开始装
        int remainCapacity = capacity;
        int i = 0;
        for (; i < goodsList.length; i++) {

            if (goodsList[i].getWeight() > remainCapacity) {
                break;
            }
            result.add(goodsList[i]);
            remainCapacity -= goodsList[i].getWeight();
        }

        // 装未装满的物品
        if (remainCapacity > 0 && i < goodsList.length) {
            BigDecimal remainValue = goodsList[i].getUnitValue().multiply(new BigDecimal(String.valueOf(remainCapacity)));
            result.add(new Goods(goodsList[i].getName(), remainCapacity, remainValue.toString()));
        }

        return result;
    }


    @Data
    public static class Goods {
        /**
         * 物品的名称
         */
        private String name;
        // 物品的重量,单位kg
        private int weight;
        // 物品的价值
        private BigDecimal value;
        // 物品的单价
        private BigDecimal unitValue;

        public Goods(String name, int weight, String value) {
            this.name = name;
            this.weight = weight;
            this.value = new BigDecimal(value);
            this.unitValue = this.value.divide(new BigDecimal(String.valueOf(weight)), 2, BigDecimal.ROUND_HALF_UP);
        }
    }

}
